// Created by WXX on 2021/9/13 10:51
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

/**
 * 执行用时：8 ms, 在所有 C++ 提交中击败了63.59%的用户
 * 内存消耗：12.9 MB, 在所有 C++ 提交中击败了40.59%的用户
 */
#define x first
#define y second

class Solution {
public:

    typedef pair<int, int> PII;

    vector<vector<int>> g;
    int n, m;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    int orangesRotting(vector<vector<int>>& grid) {
        g = grid;
        n = g.size(), m = g[0].size();
        int res = bfs();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (g[i][j] == 1) {
                    res = -1;
                }
        return res;
    }

    int bfs() {

        queue<PII> q;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (g[i][j] == 2) {
                    q.push({i, j});
                }
        int res = 0;
        while (q.size()) {
            int len = q.size();
            res++;
            while (len--) {
                auto t = q.front();
                q.pop();

                for (int i = 0; i < 4; i++) {
                    int a = t.x + dx[i], b = t.y + dy[i];
                    if (a < 0 || a >= n || b < 0 || b >= m) continue;
                    if (g[a][b] != 1) continue;
                    q.push({a, b});
                    g[a][b] = 2;
                }
            }
        }
        return max(0, res - 1);
    }
};

int main() {

    vector<vector<int>> grid = {
            {2, 1, 1},
            {1, 1, 0},
            {0, 1, 1}
    };
    cout << Solution().orangesRotting(grid) << endl;  // 4

    return 0;
}
